package class04;

import javax.naming.LimitExceededException;
import javax.swing.*;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.logging.SimpleFormatter;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MyHeap {

    public static class MyMaxHeap{
        private int[] heap;
        private final int limit;
        private int heapSize;

        public MyMaxHeap(int limit){
            heap = new int[limit];
            this.limit=limit;
            heapSize=0;
        }

        public boolean isEmpty(){
            return heapSize==0;
        }

        public boolean isFull(){
            return heapSize==limit;
        }

        public void push(int value){
            if (heapSize==limit)
                throw new RuntimeException("heap is full");
            heap[heapSize]=value;
            heapInset(heap,heapSize++);
        }

        public void heapInset(int[] arr,int index){
            while (arr[index]>arr[(index-1)/2]){
                swap(arr,index,(index-1)/2);
                index=(index-1)/2;
            }
        }

        public void swap(int[] arr ,int i ,int j){
            int tmp =  arr[i];
            arr[i]=arr[j];
            arr[j]=tmp;
        }

        public int pop(){
            int ans = heap[0];
            swap(heap,0,--heapSize);
            heapify(heap,0,heapSize);
            return ans;
        }

        public void heapify(int[] arr,int index ,int heapSize){
            int left = index*2+1;
            while (left<heapSize){
                int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
                largest = arr[largest]>arr[index]?largest:index;
                if (largest==index)
                    break;
                swap(arr,largest,index);
                index=largest;
                left=index*2+1;
            }
        }
    }
}
